package heap;

import org.junit.Test;

import java.util.Comparator;
import java.util.PriorityQueue;
/*
 *@description 数据流的中位数
 *@author hkfan
 *@version 1.0
 *@create 2025/5/16 14:13
 */
public class LeetCode_295 {

    @Test
    public void test(){
        LeetCode_295 obj = new LeetCode_295();
        obj.addNum(1);
        double param_1 = obj.findMedian();
        System.out.println(param_1);
    }

    public LeetCode_295() {

    }

    private static PriorityQueue<Integer> maxHeap;
    private static PriorityQueue<Integer> minHeap;

    private static class MaxComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1;
        }
    }

    private static class MinComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o1-o2;
        }
    }

    static {
        maxHeap = new PriorityQueue<>(new MaxComparator());
        minHeap = new PriorityQueue<>(new MinComparator());
    }


    // 添加数值
    public void addNum(int num) {
        // 1.初始情况，直接进入大根堆
        if (maxHeap.size() == 0){
            maxHeap.add(num);
            return;
        }
        // 2. 插入数值，通过判断和大根堆堆顶的大小关系，决定插入到大根堆还是小根堆
        if (num > maxHeap.peek()){
            //2.1 判断和小根堆的堆顶的大小关系
            if (minHeap.size()>0 && num > minHeap.peek()){
                minHeap.add(num);
            }else {
                maxHeap.add(num);
            }
        }else{
            maxHeap.add(num);
        }
        // 3. 调整堆
        if (Math.abs(maxHeap.size() - minHeap.size())==2 ){
            if (maxHeap.size() > minHeap.size()){
                int temp = maxHeap.poll();
                minHeap.add(temp);
            }else{
                int temp = minHeap.poll();
                maxHeap.add(temp);
            }
        }
    }

    // 返回中位数
    public Double findMedian() {
        if (maxHeap.size()==0){
            return null;
        }

        if ((maxHeap.size() + minHeap.size()) % 2 == 1) {

            return (maxHeap.size() > minHeap.size())?(double) maxHeap.peek():(double) minHeap.peek();
        }else {
            return (double) (maxHeap.peek() + minHeap.peek()) / 2;
        }

    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */